package developer.算法.图论.课程表;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
 * <p>
 * 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
 * <p>
 * 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
 * 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：numCourses = 2, prerequisites = [[1,0]]
 * 输出：true
 * 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
 * 示例 2：
 * <p>
 * 输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
 * 输出：false
 * 解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
 * <p>
 * 拓扑排序  分为 出度和入度
 * 根据维护入度还是出度 来决定走广度优先还是深度优先
 */
public class KeChengBiao {

    public static void main(String[] args) {
        shenduyouxian solutionShenDuYouXian = new shenduyouxian();
        System.out.println(solutionShenDuYouXian.canFinish(2, new int[][]{{1, 0}}));
        System.out.println(solutionShenDuYouXian.canFinish(2, new int[][]{{1, 0}, {0, 1}}));
    }


    static class shenduyouxian {
        List<List<Integer>> chudu;
        int[] search;
        boolean isCircle = false;

        public boolean canFinish(int numCourses, int[][] prerequisites) {
            chudu = new ArrayList<>(numCourses);
            search = new int[numCourses];
            isCircle = false;

            for (int i = 0; i < numCourses; i++) {
                chudu.add(new ArrayList<>());
            }

            for (int i = 0; i < prerequisites.length; i++) {
                chudu.get(prerequisites[i][1]).add(prerequisites[i][0]);
            }

            for (int i = 0; i < chudu.size(); i++) {
                dfs(i);
            }

            return !isCircle;
        }

        private void dfs(int i) {
            if (isCircle) {
                return;
            }
            search[i] = 1;//1标识查询

            List<Integer> nums = chudu.get(i);

            for (Integer num : nums) {
                if (search[num] == 0) {
                    dfs(num);
                }
                if (search[num] == 1) {
                    isCircle = true;
                    return;
                }
            }

            search[i] = 2;//2表示查询完成
        }
    }


    static class guangduyouoxiang_3 {

        List<List<Integer>> chudu = new ArrayList<>();

        public boolean canFinish(int numCourses, int[][] prerequisites) {
            for (int i = 0; i < numCourses; i++) {
                chudu.add(i, new ArrayList<>());
            }
            for (int i = 0; i < prerequisites.length; i++) {
                /*
                 * [0, 1]
                 * 想0  先1，则0 的入度是1
                 * 1 的出度是0
                 *
                 * */
                chudu.get(prerequisites[i][0]).add(prerequisites[i][1]);
            }
            dfs();
            return chudu.stream().allMatch(List::isEmpty);
        }

        private void dfs() {
            Queue<Integer> queue = new LinkedList<>();//这个是 入度为0 的数字
            for (int i = 0; i < chudu.size(); i++) {
                if (chudu.get(i).isEmpty()) {
                    queue.add(i);//入度为0的数字
                }
            }

            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    Integer poll = queue.poll();//入度为0的数据

                    for (int i1 = 0; i1 < chudu.size(); i1++) {
                        List<Integer> rudu = chudu.get(i1);
                        if (rudu.isEmpty()) {
                            continue;
                        }
                        rudu.remove(poll);
                        if (rudu.isEmpty()) {
                            queue.add(i1);
                        }
                    }
                }
            }

        }


    }


    /**
     * 拓扑排序  广度优先
     * 如果要学0  则要先学会1 则0 的入度为1
     * 以入度为0 的1 为起点 进行循环将每个拓扑排序进行remove
     */
    static class Solution_Guang_du_you_xian {

        List<List<Integer>> tuoPu;

        boolean[] hasUse;

        public boolean canFinish(int numCourses, int[][] prerequisites) {
            tuoPu = new ArrayList<>(numCourses);
            for (int i = 0; i < numCourses; i++) {
                tuoPu.add(new ArrayList<>());
            }
            hasUse = new boolean[numCourses];
            for (int i = 0; i < prerequisites.length; i++) {
                //[0,1]  先想0  先 1  则0的入度是 1
                tuoPu.get(prerequisites[i][0]).add(prerequisites[i][1]);
            }
            dfs();
            return tuoPu.stream().allMatch(List::isEmpty);
        }

        private void dfs() {
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < tuoPu.size(); i++) {
                List<Integer> integers = tuoPu.get(i);
                if (integers.isEmpty()) {//说明是起点  加入当前队列
                    hasUse[i] = true;
                    queue.offer(i);
                }
            }
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    Integer poll = queue.poll();
                    for (int j = 0; j < tuoPu.size(); j++) {
                        List<Integer> integers = tuoPu.get(j);
                        integers.remove(poll);
                        if (integers.isEmpty() && !hasUse[j]) {
                            queue.offer(j);
                            hasUse[j] = true;
                        }
                    }

                }
            }
        }

//        class Pair {
//            int idx;
//            List<Integer> val;
//
//            public Pair(int idx, List<Integer> val) {
//                this.idx = idx;
//                this.val = val;
//            }
//        }
    }

    /**
     * 拓扑排序 深度优先
     */
    static class Solution_Shen_du_you_xian {

        int[] search;
        List<List<Integer>> tuoPu = new ArrayList<>();
        boolean valid = true;//环验证

        public boolean canFinish(int numCourses, int[][] prerequisites) {

            for (int i = 0; i < numCourses; i++) {
                tuoPu.add(new ArrayList<>());
            }
            search = new int[numCourses];
            for (int i = 0; i < prerequisites.length; i++) {
                int[] prerequisite = prerequisites[i];
                //要想0  先 1 则 0->+1 [ 0,1] -> 1->
                tuoPu.get(prerequisite[1]).add(prerequisite[0]);//深度优先算法
            }

            for (int i = 0; i < numCourses; i++) {
                if (search[i] == 0) {//如果处于未搜索  则进行dfs
                    dfs(i);
                }
            }
            return valid;
        }


        public void dfs(int val) {
            search[val] = 1;// 1 表示正在搜索中
            List<Integer> chu_du = tuoPu.get(val);
            for (Integer i : chu_du) {
                if (search[i] == 0) {//表示未搜索 那么进行搜索
                    dfs(i);
                    if (!valid) {
                        return;
                    }
                }
                if (search[i] == 1) {//说明回环了
                    valid = false;
                    return;
                }
            }
            search[val] = 2;

        }
    }

    /**
     * 相关知识点 拓扑排序
     */
    class SolutionOfficial {
        List<List<Integer>> edges;
        int[] visited;
        boolean valid = true;

        public boolean canFinish(int numCourses, int[][] prerequisites) {
            edges = new ArrayList<List<Integer>>();
            for (int i = 0; i < numCourses; ++i) {
                edges.add(new ArrayList<Integer>());
            }
            visited = new int[numCourses];
            for (int[] info : prerequisites) {
                edges.get(info[1]).add(info[0]);
            }
            for (int i = 0; i < numCourses && valid; ++i) {
                if (visited[i] == 0) {
                    dfs(i);
                }
            }
            return valid;
        }

        public void dfs(int u) {
            visited[u] = 1;
            for (int v : edges.get(u)) {
                if (visited[v] == 0) {
                    dfs(v);
                    if (!valid) {
                        return;
                    }
                } else if (visited[v] == 1) {
                    valid = false;
                    return;
                }
            }
            visited[u] = 2;
        }
    }


}
